package org.everyday;

import com.common.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: Tang World
 * @Date: 22/8/2022 下午2:04
 */
public class L655 {
    //根据题意，我们可以先设计 dfs1 递归函数得到树的高度 h，以及与其相关的矩阵行列大小（并初始化矩阵）。
    //随后根据填充规则，设计 dfs2 递归函数往矩阵进行填充。
    int h, m, n;
    List<List<String>> ans;
    public List<List<String>> printTree(TreeNode root) {
        dfs1(root, 0);
        m = h + 1; n = (1 << (h + 1)) - 1;
        ans = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            List<String> cur = new ArrayList<>();
            for (int j = 0; j < n; j++) cur.add("");
            ans.add(cur);
        }
        dfs2(root, 0, (n - 1) / 2);
        return ans;
    }

    void dfs1(TreeNode root,int cur){
        if (root==null) return;
        h = Math.max(h,cur);
        dfs1(root.left,cur+1);
        dfs1(root.right,cur+1);
    }

    void dfs2(TreeNode root,int x, int y){
        if (root == null) return ;
        ans.get(x).set(y, String.valueOf(root.val));
        dfs2(root.left, x + 1, y - (1 << (h - x - 1)));
        dfs2(root.right, x + 1, y + (1 << (h - x - 1)));
    }
}
